package 链表;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 */
public class _160_相交链表 {

    /**
     * 双指针求解法
     * @param headA 链表A
     * @param headB 链表B
     * @return ListNode
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    /**
     * Hash表  两次遍历得出结论  时间复杂度O(m + n)  空间复杂度 O(m)
     * @param headA 链表A
     * @param headB 链表B
     * @return ListNode
     */
    public ListNode getIntersectionNodeHash(ListNode headA, ListNode headB) {
        Set<ListNode> hash = new HashSet<>();
        ListNode tail = headA;
        while (tail != null) {
            hash.add(tail);
            tail = tail.next;
        }

        while (headB != null) {
            if (hash.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

}
